import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = new int[]{1,1,1,3,2,2,1};
        mergeSort(arr, 0, arr.length-1);

        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr, int left, int right) {
        /**
         * 归并排序
         *  -递归实现
         * 排序思想：
         *  1，递归出去，直至仅有一个元素或没有元素时返回
         *  2，默认左右区间返回均有序，合并两个有序数组，写入当前区间*/
        // 1 递归出口
        if(left >= right) { // -排序区间中只有一个元素或者没有元素时直接返回
            return;
        }

        // 2 递归（向下递归，此时左右区间均有序）
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);

        // 3 合并（先归并至临时数组中，避免直接修改数组）
        int[] tempArray = new int[right - left + 1];
        int i = 0;
        int l1 = left;
        int l2 = mid + 1;
        while(l1 <= mid && l2 <= right) {
            if(arr[l1] <= arr[l2]) {
                tempArray[i++] = arr[l1++];
            } else {
                tempArray[i++] = arr[l2++];
            }
        }
        while(l1 <= mid) {
            tempArray[i++] = arr[l1++];
        }
        while(l2 <= right) {
            tempArray[i++] = arr[l2++];
        }

        // 4 写入至真实数组
        for(int j = 0; j < tempArray.length; j++) {
            arr[left + j] = tempArray[j];
        }
    }
}
